KCC 2021
Current Result Document :
| 한글제목(Korean Title) |
락-프리 기반 이진 탐색 트리 설계 및 구현 |
| 영문제목(English Title) |
A Design and Implementation of Lock-free based Binary Search Tree |
| 저자(Author) |
이상묵
이민욱
이상진
한재현
손용석
Sangmook Lee
Minwook Lee
Sangjin Lee
Jaehyun Han
Yongseok Son
|
| 원문수록처(Citation) |
VOL 48 NO. 01 PP. 2131 ~ 2133 (2021. 06) |
한글내용
(Korean Abstract) |
이진 탐색 트리는 빠른 탐색 속도를 가지고 원소의 추가 및 삭제가 용이한 자료구조이다. 현재 이러한 장점으로 인해 이진 탐색 트리는 자주 사용되는 자료구조 중 하나이다. 이러한 이진 탐색 트리 기반에서 여러 스레드들이 동시적으로 원소를 추가 및 삭제하기 위해서는 락킹(Locking) 기법을 필요하다. 대게 락킹 기법은 락을 획득하지 못한 스레드들이 락을 획득한 스레드가 연산을 완료할 때까지 spinning 하거나 blocking 이 되지 때문에 자료구조의 성능이 크게 떨어지게 된다. 이러한 문제를 해결하기 위해서, 본 논문에서는 atomic 연산과 access list를 이용하여 락-프리 이진 탐색 트리를 설계 및 구현한다. 이러한 atomic 연산과 access list 통해 해당 트리는 락킹 없이 동시적으로 삽입, 조회, 삭제 연산이 가능하다. 본 연구의 실험 결과에서는 제안한 기법이 기존 기법에 비해 약 10배 이상의 성능을 향상 시켰고 그 효용성을 입증시켰다. |
영문내용
(English Abstract) |
|
| 키워드(Keyword) |
|
| 파일첨부 |
PDF 다운로드
|
